package org.shj.algorithm.string;

/**
 * BM 算法也是字符串匹配的算法，要比 KMP 算法更好。
 * 思路：
 *  假设字符串是   here is a simple example
 *  模式串是      example
 * 1. 从模式串的最后一位和相应位置的字符比，此例中是 e 和 s 比，不相等，称 s 为坏字符
 * 2. 如果坏字符在模式串中不存在，则可以直接把模式串首字符的位置移到坏字符的后面。如
 *    here is a simple example
 *           example
 * 3. 仍然比较模式串的最后一位(e) 和相应位置的字符串(p)，虽然 p 是坏字符，但是它存在于模式串中，
 *    只能移动较少的位数。移动后的位置如下：
 *    here is a simple example
 *             example
 * 4. 此时 mple, ple, le, e 都可以称为好后辍, i 是坏后辍。
 * 5. 根据坏字符规则，我们应该移动字符至如下位置：
 *    here is a simple example
 *                example
 *    但是我们发现上面有4个好后辍（mple, ple, le, e），发现只有 e 在模式串的其余字符中出现过，
 *    我们就可以把其出现的最右的位置移到相应的好后辍处。也就是此处可以直接移动到如下位置：
 *    here is a simple example
 *                   example
 * 6. 此时 e 和 p 不相等，根据上面的规则，移动到如下位置：
 *    here is a simple example
 *                     example
 * 7. 得出结果
 *
 * @author Shen Huang Jian
 * @date 2019/4/13
 */
public class BM {

    public static void main(String[] args){
        String str = "here is a simple example";
        String pattern = "example";
//        String str = "abcababcabxa";
//        String pattern = "abcabx";
        int index = bm(str, pattern);

        System.out.println("符合的位置是：" + index);
    }

    /**
     *
     * @param str
     * @param pattern
     * @return 返回匹配的下标，未找到返回 -1
     */
    public static int bm(String str, String pattern){
        int patternLen = pattern.length();
        if(str.length() < patternLen){
            return -1;
        }

        int compareInd = patternLen - 1;
        char tmp;
        int move;
        while(compareInd < str.length()){
            tmp = str.charAt(compareInd);
            int lastIndex = lastIndexOf(tmp, pattern);
            if(pattern.charAt(patternLen - 1) != tmp){ // 坏字符
                if(lastIndex == -1){
                    // 坏字符不存在于模式串中
                    move = patternLen;
                }else{
                    move = patternLen - 1 - lastIndex;
                }
            }else{ //好后辍
                int n = 1;
                while(n < patternLen){
                    // 比较前一位字符是否也相等
                    if(pattern.charAt(patternLen - 1 - n) == str.charAt(compareInd - n)){
                        n++;
                        if(n == patternLen){
                            return compareInd - n + 1;
                        }
                    }else{
                        break;
                    }
                }

                //坏字符的位置
                int bad = patternLen - 1 - n;
                int index = lastIndexOf(str.charAt(compareInd - n), pattern);
                if(index == -1){
                    move = bad + 1;
                }else{
                    move = bad - index;
                }

                //下面这段逻辑未验证，个人觉得不如直接按照上面的坏字符规则移动。因为好后辍
                //可能有多个，对于每一个都求一遍在模式串中的最右位置，然后再取可移动的最大值。
                // 不仅逻辑复杂，而且比较次数，循环次数未必有所减少。
                //对于多个好后辍，求出各个好后辍在模式串中（去掉好后辍以后）最右位置的最小值
                /*int min = patternLen;
                while (n > 0){
                    //去除好后辍后的字符串
                    String newStr = pattern.substring(0, patternLen - n);
                    String goodSuffix = pattern.substring(patternLen - n);
                    lastIndex = newStr.lastIndexOf(goodSuffix);

                    min = min < lastIndex ? min : lastIndex;
                    n--;
                }
                //比较坏这符规则和这里可移动的最大值这两者之间的较大值
                */


            }
            compareInd += move;
        }
        return -1;
    }

    private static int lastIndexOf(char c, String pattern){
        char[] array = pattern.toCharArray();
        for(int i = array.length - 1; i >= 0; i--){
            if(array[i] == c){
                return i;
            }
        }
        return -1;
    }
}
